package com.ai.zuochengyun.phase01.class03;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

public class Code13_EncodeNaryTreeToBinaryTree {

    public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        a.children = List.of(b, c, d);

        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        d.children = List.of(e, f, g);

        Node i = new Node(8);
        Node k = new Node(9);
        c.children = List.of(i, k);

        BinaryTreeNode head = encode(a);
        System.out.println(head.value);
    }

    public static class Node {
        public int value;

        public List<Node> children;

        public Node(int value) {
            this.value = value;
        }

        public Node(int value, List<Node> children) {
            this.value = value;
            this.children = children;
        }
    }

    public static BinaryTreeNode encode(Node root) {
        if (root == null) {
            return null;
        }

        // 多叉树的头节点也是二叉树的头节点
        BinaryTreeNode head = new BinaryTreeNode(root.value);
        // 将后面的绑定到root的左节点
        head.left = en(root.children);
        return head;
    }

    public static BinaryTreeNode en(List<Node> children) {
        BinaryTreeNode head = null;
        BinaryTreeNode cur = null;
        if (children == null) {
            return null;
        }
        for (Node child : children) {
            BinaryTreeNode treeNode = new BinaryTreeNode(child.value);
            // 只有第一次的时候走这个逻辑
            if (head == null) {
                head = treeNode;
            } else {
                cur.right = treeNode;
            }
            cur = treeNode;
            // 深度遍历  如果有孩子节点，让它挂在当前节点的左节点上
            cur.left = en(child.children);
        }
        return head;
    }

    public static Node decode(BinaryTreeNode root) {
        if (root == null) {
            return null;
        }

        return new Node(root.value, de(root.left));
    }

    /**
     * root是第一个孩子，要将我和我的兄弟们作为一个集合，返回给父节点
     * @param root
     * @return
     */
    public static List<Node> de(BinaryTreeNode root) {
        List<Node> children = new ArrayList<>();
        while (root != null) {
            Node cur = new Node(root.value, de(root.left));
            children.add(cur);
            root = root.right;
        }
        return children;
    }
}
